public class test1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyQueue myQueue = new MyQueue();
        int len = nums.length-k+1;
        int[] res = new int[len];
        int num = 0;
        for(int i = 0;i<k;i++){
            myQueue.add(nums[i]);
        }
        res[num++] = myQueue.peek();
        for(int i = k;i<nums.length;i++){
            myQueue.poll(nums[i-k]);
            myQueue.add(nums[i]);
            res[num++] = myQueue.peek();
        }
        return res;
    }

    //注意这不是滑动窗口的问题
    //维护一个元素单调递减的队列
    class MyQueue{
        Deque<Integer> deque = new LinkedList<>();
        void add(int val){
            while(!deque.isEmpty()&&val>deque.peekLast()){
                //是while，因为如果一直大，就要一直移
                deque.removeLast();
            }
            deque.offer(val);
        }
        void poll(int val){
            //要移出的是最大值（会影响这个维护的队列），才要改变队列
            //如果移的都不是最前面的值，那对该队列也没有影响
            //peek查看的是队列的头部元素
            if(!deque.isEmpty()&&val==deque.peek()){
                deque.poll();
            }
        }
        int peek(){
            return deque.peek();
        }
    }
}
